package com.cqs.leetcode.search;

/**
 * lixw
 * 2023/10/13
 */
public class Solution378 {

    public int kthSmallest(int[][] matrix, int k) {
        int row = matrix.length, col = matrix[0].length;
        int l = matrix[0][0], r = matrix[row - 1][col - 1];
        while (l < r) {
            int mid = (r - l) / 2 + l;//==>mid可能并不是matrix中的元素
            int c = check(matrix, mid, k);
            //matrix中<k个元素不小于mid 则，第k小的元素一定在(mid, matrix[row - 1][col - 1]]中
            if (c < 0) {
                l = mid + 1;
            } else {
                //matrix中>=k个元素不小于mid 则第k小的元素一定在[matrix[0][0], mid]中
                r = mid;
            }
        }
        return r;
    }
    //1,  2
    //1,  4

    /**
     * 是否matrix中恰好有k元素<=target
     *
     * @param matrix
     * @param target
     * @param k
     * @return
     */
    private int check(int[][] matrix, int target, int k) {
        int row = matrix.length, end = matrix[0].length - 1, cnt = 0;
        for (int i = 0; i < row && end >= 0; i++) {
            //找到最后一个比mid打的元素
            while (end >= 0 && matrix[i][end] > target) {
                --end;
            }
            cnt += end + 1;
            //处理了多余k个的情况
            if (cnt > k) return 1;
        }
        return cnt == k ? 0 : -1;
    }




}
